package solutions;

import java.util.LinkedList;
import java.util.Queue;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2023-01-29
 * Time: 13:57
 */

//https://leetcode.cn/problems/number-of-islands/submissions/?envType=study-plan&id=graph-theory-basic&plan=graph&plan_progress=b2wx923

//class Solution1 {
//    //改变了原数组的值
//    //bfs
//    public int numIslands(char[][] grid) {
//        //判空
//        if (grid == null || grid.length == 0) {
//            return 0;
//        }
//        int nr = grid.length;
//        int nc = grid[0].length;
//        int nums = 0;
//        for (int i = 0; i < nr; ++i) {
//            for (int j = 0; j < nc; ++j) {
//                if (grid[i][j] == '1') {
//                    ++nums;
//                    dfs(grid, i, j);
//                }
//            }
//        }
//        return nums;
//    }
//
//    public void dfs(char[][] grid, int x, int y) {
//        int nr = grid.length;
//        int nc = grid[0].length;
//        if (x < 0 || x >= nr || y < 0 || y >= nc || grid[x][y] == '0') {
//            return;
//        }
//        grid[x][y] = '0';//将与之连接的所有'1'改为'0'
//        dfs(grid, x + 1, y);
//        dfs(grid, x, y + 1);
//        dfs(grid, x, y - 1);
//        dfs(grid, x - 1, y);
//    }
//}

//class Solution {
//    int[] dx = {1, 0, 0, -1};
//    int[] dy = {0, 1, -1, 0};
//
//    //改变了原数组的值
//    //bfs
//    public int numIslands(char[][] grid) {
//        //判空
//        if (grid == null || grid.length == 0) {
//            return 0;
//        }
//        int nr = grid.length;
//        int nc = grid[0].length;
//        int nums = 0;
//        for (int i = 0; i < nr; ++i) {
//            for (int j = 0; j < nc; ++j) {
//                if (grid[i][j] == '0') {
//                    continue;
//                }
//                Queue<int[]> queue = new LinkedList<>();
//                queue.offer(new int[]{i, j});
//                grid[i][j] = '0';
//                ++nums;
//                while (!queue.isEmpty()) {
//                    int[] cell = queue.poll();
//                    for (int k = 0; k < 4; ++k) {
//                        int mx = cell[0] + dx[k];
//                        int my = cell[1] + dy[k];
//                        if (mx >= 0 && mx < nr && my >= 0 && my < nc && grid[mx][my] == '1') {
//                            grid[mx][my] = '0';
//                            queue.offer(new int[]{mx, my});
//                        }
//                    }
//                }
//            }
//        }
//        return nums;
//    }
//}


class Solution1 {
//    public static void main(String[] args) {
//        char[][] grid = {{'1', '1', '1'}, {'0', '1', '0'}, {'1', '0', '0'}, {'1', '0', '1'}};
//        Solution1 solution1 = new Solution1();
//        solution1.numIslands(grid);
//    }
    //并查集内部类，用来调用方法和参数
    //分三步，UnionFind（初始化）, find（找根）, union（合根）
    class UnionFind {
        int count;
        int[] parent;//父节点（包括自己）
        int[] rank;//加权标记优化（避免一字长龙），表示该结点的层数（高度）

        //1. 初始化
        public UnionFind(char[][] grid) {
            count = 0;
            int m = grid.length;
            int n = grid[0].length;
            parent = new int[m * n];//所有节点
            rank = new int[m * n];//最大高度
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    if (grid[i][j] == '1') {//初始化，将每个'1'的父节点都初始化为自己
                        parent[i * n + j] = i * n + j;
                        ++count;//统计有效数据
                    }
                    rank[i * n + j] = 0;//全部初始化为0
                }
            }
        }

        //2. 找根
        public int find(int i) {
            if (parent[i] != i) {
                parent[i] = find(parent[i]);//不断查找直到找到根节点
            }
            return parent[i];
        }

        //3. 合根
        public void union(int x, int y) {
            int rootx = find(x);//x的根节点
            int rooty = find(y);//y的根节点
            if (rootx != rooty) {//x与y根节点不同
                //比较节点的层数
                if (rank[rootx] > rank[rooty]) {//rootx的层数较高
                    parent[rooty] = rootx;//将rooty指向rootx，此时rootx为二者的根节点
                } else if (rank[rootx] < rank[rooty]) {//同理
                    parent[rootx] = rooty;
                } else {//层数相同
                    parent[rooty] = rootx;//任意指向
                    rank[rootx] += 1;//层数加1（A，B（层数1），A->B,此时B的层数变为2）
//                    parent[rootx] = rooty;//另一种
//                    rank[rooty] += 1;
                }
                --count;//两个节点能够联通，就看作一个节点，即有效节点减1
            }
        }

        public int getCount() {
            return count;
        }
    }

    public int numIslands(char[][] grid) {
        if (grid == null || grid.length == 0) {
            return 0;
        }

        int nr = grid.length;
        int nc = grid[0].length;
        UnionFind uf = new UnionFind(grid);
        for (int r = 0; r < nr; ++r) {
            for (int c = 0; c < nc; ++c) {
                if (grid[r][c] == '1') {
                    grid[r][c] = '0';
                    //根据遍历顺序（从头开始）可知，不必判断左和上
                    //若是指定任意位置，（上下左右缺一不可）
//                    if (r - 1 >= 0 && grid[r - 1][c] == '1') {
//                        uf.union(r * nc + c, (r - 1) * nc + c);
//                    }
                    if (r + 1 < nr && grid[r + 1][c] == '1') {
                        uf.union(r * nc + c, (r + 1) * nc + c);
                    }
//                    if (c - 1 >= 0 && grid[r][c - 1] == '1') {
//                        uf.union(r * nc + c, r * nc + c - 1);
//                    }
                    if (c + 1 < nc && grid[r][c + 1] == '1') {
                        uf.union(r * nc + c, r * nc + c + 1);
                    }
                }
            }
        }

        return uf.getCount();
    }
}

